#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_SIZE 100

typedef struct {
	char data[MAX_SIZE];
	int top;
} Stack;

// 栈操作
void initStack(Stack *s) {
	s->top = -1;
}

int isFull(Stack *s) {
	return s->top == MAX_SIZE - 1;
}

int isEmpty(Stack *s) {
	return s->top == -1;
}

void push(Stack *s, char c) {
	if (!isFull(s)) {
		s->data[++(s->top)] = c;
	}
}

char pop(Stack *s) {
	if (!isEmpty(s)) {
		return s->data[(s->top)--];
	}
	return '\0'; // 返回空字符
}

char peek(Stack *s) {
	if (!isEmpty(s)) {
		return s->data[s->top];
	}
	return '\0'; // 返回空字符
}

// 检查括号匹配
int checkBrackets(const char *expr) {
	Stack s;
	initStack(&s);
	
	for (int i = 0; expr[i] != '\0'; i++) {
		char c = expr[i];
		
		if (c == '(' || c == '[' || c == '{') {
			push(&s, c);
		} else if (c == ')' || c == ']' || c == '}') {
			if (isEmpty(&s)) return 0; // 没有相应的开括号
			
			char open = pop(&s);
			if ((c == ')' && open != '(') || 
				(c == ']' && open != '[') || 
				(c == '}' && open != '{')) {
				return 0; // 括号不匹配
			}
			if (c == ')' && (peek(&s) == ']' || peek(&s) == '}')) {
				return 0; // 小括号中不能有大括号或方括号
			}
		}
	}
	
	return isEmpty(&s); // 栈为空则括号匹配
}

// 检查表达式的合法性
int isValidExpression(const char *expr) {
	int len = strlen(expr);
	if (len == 0) return 0;
	
	if (isspace(expr[0]) || isspace(expr[len - 1])) return 0; // 表达式不能以空格开头或结尾
	
	for (int i = 0; i < len; i++) {
		
		char c = expr[i];
		
		if (!isdigit(c) && !isspace(c) && c != '+' && c != '-' && c != '*' && c != '/' &&
			c != '(' && c != ')' && c != '[' && c != ']' && c != '{' && c != '}') {
			return 0; // 包含非法字符
		}
		
// 检查操作符和操作数的合法顺序
		if (i > 0 && ((c == '+' || c == '-' || c == '*' || c == '/') &&
			(expr[i - 1] == '+' || expr[i - 1] == '-' || expr[i - 1] == '*' || expr[i - 1] == '/'))) {
			return 0; // 连续操作符
		}
		
		if (i > 0 && ((c == ')' || c == ']' || c == '}') && 
			(expr[i - 1] == '+' || expr[i - 1] == '-' || expr[i - 1] == '*' || expr[i - 1] == '/'))) {
			return 0; // 闭括号后不能是操作符
		}
		
		if (i < len - 1 && (c == '(' || c == '[' || c == '{') &&
			(expr[i + 1] == '+' || expr[i + 1] == '-' || expr[i + 1] == '*' || expr[i + 1] == '/')) {
			return 0; // 开括号后不能是操作符
		}
	}
	
	return 1;
}

// 计算表达式的值（使用逆波兰表示法）
int precedence(char op) {
	if (op == '+' || op == '-') return 1;
	if (op == '*' || op == '/') return 2;
	return 0;
}

int applyOp(int a, int b, char op) {
	switch (op) {
		case '+': return a + b;
		case '-': return a - b;
		case '*': return a * b;
		case '/': return a / b;
	}
	return 0;
}

int evaluateExpression(const char *expr) {
	Stack values, ops;
	initStack(&values);
	initStack(&ops);
	
	for (int i = 0; expr[i] != '\0'; i++) {
		if (isspace(expr[i])) continue;
		
		if (isdigit(expr[i])) {
			int val = 0;
			while (i < strlen(expr) && isdigit(expr[i])) {
				val = val * 10 + (expr[i] - '0');
				i++;
			}
			i--; // 调整 i 位置
			push(&values, val);
		} else if (expr[i] == '(' || expr[i] == '[' || expr[i] == '{') {
			push(&ops, expr[i]);
		} else if (expr[i] == ')' || expr[i] == ']' || expr[i] == '}') {
			while (!isEmpty(&ops) && peek(&ops) != '(' && peek(&ops) != '[' && peek(&ops) != '{') {
				int val2 = pop(&values);
				int val1 = pop(&values);
				char op = pop(&ops);
				push(&values, applyOp(val1, val2, op));
			}
			pop(&ops); // 弹出开括号
		} else {
			while (!isEmpty(&ops) && precedence(peek(&ops)) >= precedence(expr[i])) {
				int val2 = pop(&values);
				int val1 = pop(&values);
				char op = pop(&ops);
				push(&values, applyOp(val1, val2, op));
			}
			push(&ops, expr[i]);
		}
	}
	
	while (!isEmpty(&ops)) {
		int val2 = pop(&values);
		int val1 = pop(&values);
		char op = pop(&ops);
		push(&values, applyOp(val1, val2, op));
	}
	
	return pop(&values); // 返回结果
}

int main() {
	char expr[MAX_SIZE];
	printf("请输入中缀表达式: ");
	fgets(expr, sizeof(expr), stdin);
	
// 去掉末尾的换行符
	size_t len = strlen(expr);
	if (len > 0 && expr[len - 1] == '\n') {
		expr[len - 1] = '\0';
	}
	
	if (!checkBrackets(expr)) {
		printf("表达式中的括号不匹配。\n");
		return 1;
	}
	
	if (!isValidExpression(expr)) {
		printf("表达式不合法。\n");
		return 1;
	}
	
	int result = evaluateExpression(expr);
	printf("表达式的计算结果是: %d\n", result);
	
	return 0;
}

